#include<iostream>
using std::endl;
using std::cout;
#include<vector>
using std::vector;
#include <math.h>
#include <set>
template<typename T>
void swap(T &a,T &b){
    T temp = a;
    a = b;
    b = temp;
}
template<typename T,typename Compare=std::less<T>> 
class MyQsort 
{ 
public:     
    MyQsort(T *arr, size_t size, Compare com);     
    void quick(int left, int right, Compare &com);     
    int partition(int left, int right, Compare &com);     
    void print(); 
private:    
    vector<T> _vec; 
};
template<typename T,typename Compare> 
void MyQsort<T,Compare>::print(){
    for(auto &ele : _vec){
        cout<<ele<<" ";
    }
    cout<<endl;
}
template<typename T,typename Compare> 
int MyQsort<T,Compare>::partition(int left, int right, Compare &com){
//int part(vector<int>&arr, int low, int hight)  //划分函数

	int i = left, j = right;
    T pivot = _vec[left]; //基准元素
	while (i < j)
	{
		while (i<j && com(pivot,_vec[j])) //从右向左开始找一个 小于等于 pivot的数值
		{
			j--;
		}
		if (i < j)
		{
			swap(_vec[i++], _vec[j]);  //r[i]和r[j]交换后 i 向右移动一位
		}
		while (i < j && com(_vec[i],pivot)) //从左向右开始找一个 大于 pivot的数值
		{
			i++;
		}
		if (i < j)
		{
			swap(_vec[i], _vec[j--]);  //r[i]和r[j]交换后 i 向左移动一位
		}
	}
	return i;  //返回最终划分完成后基准元素所在的位置
}

template<typename T,typename Compare> 
void MyQsort<T,Compare>::quick(int left, int right, Compare &com){
    int mid;
    if(left<right){
        mid = partition(left,right,com);
        quick(left,mid-1,com);
        quick(mid+1,right,com);
    }
}

template<typename T,typename Compare> 
MyQsort<T,Compare>::MyQsort(T *arr, size_t size, Compare com){
    for(size_t i = 0;i<size;i++){
        _vec.push_back(arr[i]);
    }
    quick(0,_vec.size()-1,com);
}

int test(){
    int arr[]={12,1,7,9,18,22,25};
    MyQsort<int> myqsort(arr,sizeof(arr)/sizeof(arr[0]),std::less<int>());
    myqsort.print();
}

class Point
{
public:
    Point(int ix = 0, int iy = 0)
    : _ix(ix)
    , _iy(iy)
    {
    }

    double getDistance() const
    {
        return hypot(_ix, _iy);
    }

    int getX() const
    {
        return _ix;
    }

    int getY() const
    {
        return _iy;
    }

    ~Point()
    {
    }

    friend std::ostream &operator<<(std::ostream &os, const Point &rhs);
private:
    int _ix;
    int _iy;
};

std::ostream &operator<<(std::ostream &os, const Point &rhs)
{
    os << "(" << rhs._ix
       << ", " << rhs._iy
       << ")";

    return os;
}
bool operator<(const Point &lhs, const Point &rhs)
{
    if(lhs.getDistance() < rhs.getDistance())
    {
        return true;
    }
    else if(lhs.getDistance() == rhs.getDistance())
    {
        if(lhs.getX() < rhs.getX())
        {
            return true;
        }
        else if(lhs.getX() == rhs.getX())
        {
            if(lhs.getY() < rhs.getY())
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}

int test1(){
    Point arr[] = {
        Point(1, 2),
        Point(-1, 2),
        Point(9, 4),
        Point(4, 2),
        Point(1, 2),
        Point(1, -2),
        Point(3, 2),
    };
    MyQsort<Point> myPointq(arr,sizeof(arr)/sizeof(arr[0]),std::less<Point>());
    myPointq.print();
}
void test2(){
    vector<int> arr1({7,8,9,5,2,17,18,1,20,21});
    //MyQsort<int> myInt(arr1,arr1.size(),std::less<int>());

}

int main(){
    test1();
}